English+GermanWikipedia - /page/entry.mu

Micron Document

<!DOCTYPE html>

<title>Tabu-Suche</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Tabu-Suche</span></h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr"><p><b>Tabu-Suche</b> ist ein iteratives <a href="Metaheuristik" title="Metaheuristik">metaheuristisches</a> Verfahren zur Lösung oder Annäherung von komplexen Problemen. Der Algorithmus wurde 1986 von <a href="Fred_W._Glover" title="Fred W. Glover">Fred W. Glover</a> in den USA erfunden<sup id="cite_ref-glover86_1-0" class="reference"><a href="#cite_note-glover86-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> und seither ständig weiterentwickelt.

</p><p>So wie beispielsweise <a href="Evolution%C3%A4rer_Algorithmus" title="Evolutionärer Algorithmus">evolutionäre Algorithmen</a> ist auch die Tabu-Suche ein heuristisches <a href="Optimierungsverfahren" class="mw-redirect" title="Optimierungsverfahren">Optimierungsverfahren</a>. Anders als bei evolutionären Algorithmen wird bei der klassischen Tabu-Suche in jedem Iterationsschritt von nur einer Lösung ausgegangen. Die Tabu-Suche ist also ein <a href="Trajektorie_(Mathematik)" title="Trajektorie (Mathematik)">trajektionsbasiertes</a> Verfahren, da dessen Ablauf einer <a href="Phasenraum#Beispiel_einer_Phasenraumanalyse" title="Phasenraum">Trajektorie</a> im Suchraum folgt.

</p>

<div class="mw-heading mw-heading2"><h2 id="Grundidee">Grundidee</h2></div>

<p>Um Zyklen beim Traversieren des Lösungsraumes zu vermeiden, wird bei der Tabu-Suche mit Hilfe während der Suche gesammelter Daten eine <i>Tabu-Liste</i> erstellt. Die auf dieser Liste stehenden Züge oder Lösungen dürfen in der aktuellen Iteration nicht oder nur bei zusätzlicher Erfüllung eines Aspirationskriteriums ausgeführt werden.

</p><p>Eine klassische und schnell zu implementierende <i>Tabu-Strategie</i> ist dabei, das Komplement des in einer Iteration ausgeführten Zuges für eine bestimmte <i>Tabu-Dauer</i> in der Tabu-Liste zu speichern. Ein anderer Ansatz verbietet die Veränderung von bestimmten Teilbereichen einer Lösung für eine bestimmte Zeit.

</p>

<div class="mw-heading mw-heading2"><h2 id="Ablauf">Ablauf</h2></div>

<ol><li>In der <i>Eingangsphase</i> wird (zum Beispiel zufällig oder nach einer geeigneten Heuristik) eine Initial-Lösung erzeugt, von der aus der Algorithmus startet. Danach beginnt die eigentliche Optimierung.</li>

<li>Von der aktuellen Lösung ausgehend erzeugt man eine <i>Nachbarschaft</i> von Lösungen. Dies stützt sich auf das Vorhandensein einer Nachbarschaftsfunktion <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N(x)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ca1ee5a5ef6497108b2f6d7f1fc8a224a52062fa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.203ex; height:2.843ex;" alt="{\displaystyle N(x)}" loading="lazy"></span>. Die von dieser Funktion erzeugte Menge von benachbarten Lösungen zu <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"></span> sollte zumindest ein Element beinhalten.</li>

<li>Danach erfolgt die Auswahl einer neuen Lösung. Eine Lösung wird als die aktuelle gewählt, wenn sie die beste Lösung der Nachbarschaft darstellt und nicht als Tabu klassifiziert worden ist (Tabu-Kriterium).</li>

<li>Ausgehend vom ausgeführten Zug wird die Tabu-Liste aktualisiert. Je nach gewählter Tabu-Strategie kann zum Beispiel das Komplement des Zuges für eine bestimmte Anzahl an Iterationen tabuisiert werden.</li></ol>

<div class="mw-heading mw-heading2"><h2 id="Pseudocode">Pseudocode</h2></div>

<pre>aktuelleLösung = ErzeugeStartLösung()

SOLANGE (Abbruchkriterium nicht erfüllt)

nachbarschaft = ErzeugeNachbarschaft(aktuelleLösung)

Evaluiere(nachbarschaft)

nachbarschaft = EntferneTabuZüge(nachbarschaft)

aktuelleLösung = WähleBestenZug(nachbarschaft)

Tabuisiere(AusgeführtenZug, TabuDauer)

ENDE SOLANGE

</pre>

<div class="mw-heading mw-heading2"><h2 id="Quellen">Quellen</h2></div>

<li id="cite_note-glover86-1"><span class="mw-cite-backlink"><a href="#cite_ref-glover86_1-0">↑</a></span> <span class="reference-text">F. Glover and C. McMillan: <cite class="lang" lang="en" dir="auto" style="font-style:italic">The general employee scheduling problem: an integration of MS and AI</cite>. In: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Computers and Operations Research</cite>. 1986 (englisch).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Tabu-Suche&rft.atitle=The+general+employee+scheduling+problem%3A+an+integration+of+MS+and+AI&rft.au=F.+Glover+and+C.+McMillan&rft.btitle=Computers+and+Operations+Research&rft.date=1986&rft.genre=book" style="display:none"> </span></span>

</li>

</ol>

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li>F. Glover: <i>Future paths for integer programming and links to artificial intelligence.</i> In: <i>Comput. Oper. Res.</i> 13, 1986, S. 533–549.</li>

<li>F. Glover, M. Laguna: 1997. <i>Tabu Search.</i> Kluwer Academic Publishers, 1997.</li>

<li>R. Battiti, G. Tecchiolli: <i>The reactive tabu search.</i> In: <i>ORSA J. Comput.</i> 6, 2, 1994, S. 126–140.</li>

<li>A. Heinrici: <i>Leistungsvergleich von Nachbarschaftssuchverfahren.</i> VWF Verlag für Wissenschaft und Forschung, Berlin, 1996, ISBN 3-930324-76-8.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<ul><li><a rel="nofollow" class="external text" href="https://leeds-faculty.colorado.edu/glover/tabusearchvignettes.html"><i>Tabu Search Vignettes.</i></a> Tabu-Suche auf Fred Glovers Homepage (englisch).</li></ul></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2023-11-12" href="https://de.wikipedia.org/wiki/?title=Tabu-Suche&oldid=239040381">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>